import java.util.*;

//火星词典
//测试链接：https://leetcode.cn/problems/Jf1JuT/description/
public class AlienOrder {
    Map<Character, Set<Character>> edges = new HashMap<>();  //存放邻接表
    Map<Character,Integer> in = new HashMap<>();  //存放入度信息
    boolean check = false;  //判断是否合法

    public String alienOrder(String[] words) {
        for(String s : words)
            for(int i = 0; i < s.length(); i++)
                in.put(s.charAt(i), 0);   //先统计包含哪些字母

        //创建邻接表
        int n = words.length;
        for(int i = 0; i < n; i++) {
            for(int j = i+1; j < n; j++) {
                create(words[i], words[j]);   //写一个create函数建表
                if(check) return "";
            }
        }

        //进行拓扑排序
        Queue<Character> q = new LinkedList<>();
        StringBuilder ans = new StringBuilder();
        //先把入度为0的点放入队列
        for(char c : in.keySet()) {
            if(in.get(c) == 0) q.add(c);
        }

        while(!q.isEmpty()) {
            char c = q.poll();
            ans.append(c);

            if(!edges.containsKey(c)) continue;
            //将c指向的节点入度-1
            for(char temp : edges.get(c)) {
                in.put(temp, in.get(temp)-1);

                if(in.get(temp) == 0) {
                    q.add(temp);
                }
            }
        }

        //判断是否存在环
        for(char c : in.keySet()) {
            if(in.get(c) != 0) return "";
        }

        return ans.toString();
    }

    public void create(String str1, String str2) {
        int n = Math.min(str1.length(), str2.length());
        int i = 0;  //定义一个指针去循环扫描两个字符串，找到不同的位置
        for( ; i < n; i++) {
            char c1 = str1.charAt(i);
            char c2 = str2.charAt(i);

            if(!edges.containsKey(c1)) {
                edges.put(c1, new HashSet<>());
            }
            if(c1 != c2) {   //c1 - > c2

                if(!edges.get(c1).contains(c2)) {
                    edges.get(c1).add(c2);
                    in.put(c2, in.get(c2)+1); //c2的入度数量+1
                }
                break;
            }
        }
        //判断是否合法
        if(i == str2.length() && i < str1.length()) check = true;
    }
}
